// Copyright (c) 2005-2008, Simon Howard
// Permission to use, copy, modify, and/or distribute this software
// for any purpose with or without fee is hereby granted, provided
// that the above copyright notice and this permission notice appear
// in all copies.
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
// WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
// AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
// CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
// NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

use std::collections::HashSet;
use std::hash::{BuildHasher, Hash, Hasher};

/// A trait for hash functions that can be used with the Bloom filter.
pub trait HashFunction {
    fn hash(&self, data: &[u8]) -> u64;
}

/// A struct representing a Bloom filter.
pub struct BloomFilter<H: HashFunction> {
    buffer: Vec<bool>,
    hash_function: H,
    num_salts: usize,
}

impl<H: HashFunction> BloomFilter<H> {
    /// Creates a new Bloom filter with the specified buffer size, hash function, and number of salts.
    pub fn new(buffer_size: usize, hash_function: H, num_salts: usize) -> Option<Self> {
        if num_salts == 0 || buffer_size == 0 {
            return None;
        }
        Some(Self {
            buffer: vec![false; buffer_size],
            hash_function,
            num_salts,
        })
    }

    /// Inserts an item into the Bloom filter.
    pub fn insert(&mut self, item: &str) {
        let hashes = self.compute_hashes(item);
        for hash in hashes {
            let index = hash % self.buffer.len() as u64;
            self.buffer[index as usize] = true;
        }
    }

    /// Queries the Bloom filter to check if an item might be present.
    pub fn query(&self, item: &str) -> bool {
        let hashes = self.compute_hashes(item);
        hashes.iter().all(|hash| {
            let index = hash % self.buffer.len() as u64;
            self.buffer[index as usize]
        })
    }

    /// Reads the current state of the Bloom filter into a byte array.
    pub fn read(&self, state: &mut [u8]) {
        let bytes_per_bool = std::mem::size_of::<bool>();
        for (i, &bit) in self.buffer.iter().enumerate() {
            let byte_index = i / bytes_per_bool;
            let bit_index = i % bytes_per_bool;
            if bit {
                state[byte_index] |= 1 << bit_index;
            }
        }
    }

    /// Loads the state of the Bloom filter from a byte array.
    pub fn load(&mut self, state: &[u8]) {
        let bytes_per_bool = std::mem::size_of::<bool>();
        for (i, bit) in self.buffer.iter_mut().enumerate() {
            let byte_index = i / bytes_per_bool;
            let bit_index = i % bytes_per_bool;
            *bit = (state[byte_index] & (1 << bit_index)) != 0;
        }
    }

    /// Computes the hashes for an item using the hash function and salts.
    fn compute_hashes(&self, item: &str) -> Vec<u64> {
        let mut hashes = Vec::new();
        for salt in 0..self.num_salts {
            let mut hasher = self.hash_function.hash;
            hasher.write(item.as_bytes());
            hasher.write_usize(salt);
            hashes.push(hasher.finish());
        }
        hashes
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    /// A simple hash function for testing purposes.
    struct TestHashFunction;

    impl HashFunction for TestHashFunction {
        fn hash(&self, data: &[u8]) -> u64 {
            let mut hasher = std::collections::hash_map::DefaultHasher::new();
            data.hash(&mut hasher);
            hasher.finish()
        }
    }

    #[test]
    fn test_bloom_filter_new_free() {
        let filter = BloomFilter::new(128, TestHashFunction, 1);
        assert!(filter.is_some());
        let filter = BloomFilter::new(128, TestHashFunction, 64);
        assert!(filter.is_some());
        let filter = BloomFilter::new(128, TestHashFunction, 50000);
        assert!(filter.is_none());
    }

    #[test]
    fn test_bloom_filter_insert_query() {
        let mut filter = BloomFilter::new(128, TestHashFunction, 4).unwrap();
        assert!(!filter.query("test 1"));
        assert!(!filter.query("test 2"));
        filter.insert("test 1");
        filter.insert("test 2");
        assert!(filter.query("test 1"));
        assert!(filter.query("test 2"));
    }

    #[test]
    fn test_bloom_filter_read_load() {
        let mut filter1 = BloomFilter::new(128, TestHashFunction, 4).unwrap();
        filter1.insert("test 1");
        filter1.insert("test 2");
        let mut state = [0u8; 16];
        filter1.read(&mut state);
        let mut filter2 = BloomFilter::new(128, TestHashFunction, 4).unwrap();
        filter2.load(&state);
        assert!(filter2.query("test 1"));
        assert!(filter2.query("test 2"));
    }

    #[test]
    fn test_bloom_filter_intersection() {
        let mut filter1 = BloomFilter::new(128, TestHashFunction, 4).unwrap();
        filter1.insert("test 1");
        filter1.insert("test 2");
        let mut filter2 = BloomFilter::new(128, TestHashFunction, 4).unwrap();
        filter2.insert("test 1");
        assert!(!filter2.query("test 2"));
        let mut result = BloomFilter::new(128, TestHashFunction, 4).unwrap();
        for (i, &bit) in filter1.buffer.iter().enumerate() {
            result.buffer[i] = bit && filter2.buffer[i];
        }
        assert!(result.query("test 1"));
        assert!(!result.query("test 2"));
    }

    #[test]
    fn test_bloom_filter_union() {
        let mut filter1 = BloomFilter::new(128, TestHashFunction, 4).unwrap();
        filter1.insert("test 1");
        let mut filter2 = BloomFilter::new(128, TestHashFunction, 4).unwrap();
        filter2.insert("test 2");
        let mut result = BloomFilter::new(128, TestHashFunction, 4).unwrap();
        for (i, &bit) in filter1.buffer.iter().enumerate() {
            result.buffer[i] = bit || filter2.buffer[i];
        }
        assert!(result.query("test 1"));
        assert!(result.query("test 2"));
    }

    #[test]
    fn test_bloom_filter_mismatch() {
        let filter1 = BloomFilter::new(128, TestHashFunction, 4).unwrap();
        let filter2 = BloomFilter::new(64, TestHashFunction, 4);
        assert!(filter2.is_none());
        let filter2 = BloomFilter::new(128, TestHashFunction, 32);
        assert!(filter2.is_none());
    }
}
